// hdu3397
// 题意：给定长度为n(<=100000)的0,1序列，要进行m(<=100000)次操作，
//       一共有5种操作：
//        1.将区间 [l, r] 置0;
//        2.将区间 [l, r] 置1;
//        3.将区间 [l, r] 内0, 1翻转;
//        4.输出区间 [l, r] 内1的个数;
//        5.输出区间 [l, r] 内最长连续1的个数;
//
// 题解：经典题了。可能有其他更简洁的方法，我的方法是每个线段树节点维护
//       一个覆盖标记（1表示全被0覆盖，2表示全被1覆盖，0表示其他），一个
//       翻转标记，然后是维护左边界最长连续0或1, 右边界最长0或1，整个
//       区间最长连续0或1。然后就是拼命维护这些信息。
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <cstring>

int const maxn = 100007;

struct node
{
	int cover; // 1: cover all white, 2: all black
	bool flip;
	int count;
	int lb, rb; // left, right black
	int lw, rw; // left, right white
	int llb, llw; // longest black, white
} tree[4 * maxn];

int n, m;

void set_node(int id, int opt, int len)
{
	node & t = tree[id];
	t.lw = t.rw = t.llw = (opt == 1 ? len : 0);
	t.lb = t.rb = t.llb = (opt != 1 ? len : 0);
}

void swap_node(int id)
{
	node & t = tree[id];
	std::swap(t.lw, t.lb);
	std::swap(t.rw, t.rb);
	std::swap(t.llw, t.llb);
}

void push_down(int id, int l, int r)
{
	node & t = tree[id];
	int mid = (l + r) / 2;
	int tl = mid - l + 1;
	int tr = r - mid;
	if (t.cover) {
		tree[id * 2].cover = tree[id * 2 + 1].cover = t.cover;
		tree[id * 2].flip = false;
		tree[id * 2 + 1].flip = false;
		tree[id * 2].count = (t.cover - 1) * tl;
		tree[id * 2 + 1].count = (t.cover - 1) * tr;

		set_node(id * 2, t.cover, tl);
		set_node(id * 2 + 1, t.cover, tr);
		t.cover = 0;
	}

	if (t.flip) {
		tree[id * 2].flip ^= true;
		tree[id * 2 + 1].flip ^= true;
		tree[id * 2].count = tl - tree[id * 2].count;
		tree[id * 2 + 1].count = tr - tree[id * 2 + 1].count;

		swap_node(id * 2);
		swap_node(id * 2 + 1);
		t.flip = false;
	}
}

void push_up(int id, int l, int r)
{
	int mid = (l + r) / 2;
	int totl = mid - l + 1, totr = r - mid;
	node & t = tree[id];
	t.lb = tree[id * 2].lb;  t.rb = tree[id * 2 + 1].rb;
	t.lw = tree[id * 2].lw;  t.rw = tree[id * 2 + 1].rw;
	t.llb = std::max(tree[id * 2].llb, tree[id * 2 + 1].llb);
	t.llw = std::max(tree[id * 2].llw, tree[id * 2 + 1].llw);
	if (t.lb == totl) t.lb += tree[id * 2 + 1].lb;
	if (t.lw == totl) t.lw += tree[id * 2 + 1].lw;
	if (t.rb == totr) t.rb += tree[id * 2].rb;
	if (t.rw == totr) t.rw += tree[id * 2].rw;

	t.llb = std::max(t.llb, tree[id * 2].rb + tree[id * 2 + 1].lb);
	t.llw = std::max(t.llw, tree[id * 2].rw + tree[id * 2 + 1].lw);
	t.count = tree[id * 2].count + tree[id * 2 + 1].count;
}

void update(int id, int l, int r, int tl, int tr, int opt)
{
	node & t = tree[id];
	if (tl <= l && r <= tr) {
		if (opt == 3) {
			t.flip ^= true;
			t.count = r - l + 1 - t.count;
			swap_node(id);
		} else {
			t.cover = opt;
			t.flip = false;
			t.count = (opt - 1) * (r - l + 1);
			set_node(id, t.cover, r - l + 1);
		}
		return;
	}
	int mid = (l + r) / 2;
	push_down(id, l, r);
	if (tl <= mid) update(id * 2, l, mid, tl, tr, opt);
	if (mid < tr) update(id * 2 + 1, mid + 1, r, tl, tr, opt);
	push_up(id, l, r);
}

int query(int id, int l, int r, int tl, int tr, int opt)
{
	if (tl <= l && r <= tr)
		return opt == 1 ? tree[id].count : tree[id].llb;
	push_down(id, l, r);
	int mid = (l + r) / 2, ret = 0;
	if (opt == 1) {
		if (tl <= mid) ret += query(id * 2, l, mid, tl, tr, opt);
		if (mid < tr) ret += query(id * 2 + 1, mid + 1, r, tl, tr, opt);
	} else {
		ret = std::max(ret,
				std::min(tr, mid + tree[id * 2 + 1].lb) - std::max(tl, mid - tree[id * 2].rb + 1) + 1);
		if (tl <= mid) ret = std::max(ret, query(id * 2, l, mid, tl, tr, opt));
		if (mid < tr) ret = std::max(ret, query(id * 2 + 1, mid + 1, r, tl, tr, opt));
	}
	return ret;
}

void build(int id, int l, int r)
{
	node & t = tree[id];
	t.flip = false;
	t.cover = 0;
	if (l == r) {
		std::cin >> t.count;
		set_node(id, t.count + 1, 1);
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	push_up(id, l, r);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		build(1, 1, n);
		for (int i = 0, opt, l, r; i < m; i++) {
			std::cin >> opt >> l >> r;
			l++; r++;
			if (opt <= 2)
				update(1, 1, n, l, r, opt + 1);
			else
				std::cout << query(1, 1, n, l, r, opt - 2) << '\n';
	}
	}
}

